package leetcode.problems.P146LRU缓存;


import java.util.*;

public class LRUCache {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        Integer integer = list.removeLast();
        System.out.println(integer);
    }
}

// 自定义双链表+哈希表存储链表节点
class LRUCache0 {
    private int capacity;
    private Map<Integer, Node> cacheMap; // key -> Node
    private Node dummy;
    private Node tail;

    public LRUCache0(int capacity) {
        dummy = new Node();
        this.capacity = capacity;
        cacheMap = new HashMap<>();
    }

    public int get(int key) {
        if (cacheMap.containsKey(key)) {
            Node node = cacheMap.get(key);
            moveToHead(node);
            return node.value;
        }
        return -1;
    }


    public void put(int key, int value) {
        if (cacheMap.containsKey(key)) {
            Node node = cacheMap.get(key);
            moveToHead(node);// head(new) -> tail(old)
            node.value = value;
            return;
        }
        Node node = new Node(key, value);
        cacheMap.put(key, node);
        insertOnHead(node);
        if (cacheMap.size() > capacity) {
            int rmKey = removeTail();
            cacheMap.remove(rmKey);
        }
    }

    private int removeTail() {
        if (tail == null) return -1;
        int key = tail.key;
        tail.prev.next = null;
        if (tail.prev != dummy) tail = tail.prev;
        else tail = null;
        return key;
    }

    // 将链表中的某个节点移动到链表头
    private void moveToHead(Node node) {
        if (dummy.next == node) return;
        Node second = dummy.next;
        // 维护链表中原节点的链接关系
        node.prev.next = node.next;
        if (node.next != null) node.next.prev = node.prev;
        else {// node为链表尾部节点
            tail = node.prev;// 更新tail
        }
        dummy.next = second.prev = node;
        node.prev = dummy;
        node.next = second;
    }

    // 将新节点插入链表头
    private void insertOnHead(Node node) {
        if (dummy.next == null) {
            dummy.next = tail = node;
            node.prev = dummy;
            return;
        }
        Node second = dummy.next;
        second.prev = dummy.next = node;
        node.next = second;
        node.prev = dummy;
    }

    private static class Node {
        int key;
        int value;
        Node next;
        Node prev;

        Node() {
        }

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

// 使用LinkedHashMap实现
class LRUCache1 extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache1(int capacity) {
        super(capacity, 0.75F, true);// accessOrder=true, 保证访问顺序
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    // 移除最旧的元素条件
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {
        return super.size() > capacity;
    }
}

// 使用双端队列+哈希表实现
class LRUCache2 {
    Deque<Integer> q;
    Map<Integer, Integer> map;
    int n;

    public LRUCache2(int capacity) {
        q = new LinkedList<>();
        map = new HashMap<>();
        n = capacity;
    }

    public int get(int key) {
        int ret = -1;
        if (map.containsKey(key)) {
            ret = map.get(key);
            q.remove(key);// 从末尾移除
            q.addFirst(key);// 从首部添加
        }
        return ret;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {//首先判断是否包含键
            q.remove(key);
        } else if (q.size() == n) {// 不包含，需要插入该元素，但容量满了
            map.remove(q.removeLast());//淘汰队尾元素
        }
        q.addFirst(key);// 添加到队首
        map.put(key, value);
    }
}